package uk.ac.strath.cis.metric_spaces.indices;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import uk.ac.strath.cis.metric_spaces.distance.StructuralEntropicDistance;
import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.ProcessableDistance;

public class SedTree<E> extends AbstractMetricIndex<E> {

	private E root;
	private SedTree<E> left;
	private SedTree<E> right;

	public SedTree(Distance<E> metric) {
		super(metric);
	}

	public SedTree(SedTree<E> copy) {
		super(copy);
	}

	public void insert(Set<E> elements) {
		super.insert(elements);
		insert(new ArrayList<E>(elements));
	}

	private void insert(List<E> elements) {
		if (elements.size() == 1) {
			root = elements.get(0);
		} else if (elements.size() > 1) {
			root = selectRoot(elements);
			elements.remove(root);
			if(root == null) throw new NullPointerException("root is null");

			List<E> a = elements.subList(0, (elements.size() / 2));
			List<E> b = elements.subList((elements.size() / 2),
					elements.size());
			List<E> a_ = new ArrayList<E>(a);
			a_.add(root);

			List<E> b_ = new ArrayList<E>(b);
			b_.add(root);

			if (!a.isEmpty() || !b.isEmpty()) {
				if (distance(a_) <= distance(b_)) {
					left = makeSubTree(a);
					right = makeSubTree(b);
				} else {
					left = makeSubTree(b);
					right = makeSubTree(a);
				}
			}
		}
	}

	private SedTree<E> makeSubTree(List<E> elements) {
		SedTree<E> subtree = null;
		if (!elements.isEmpty()) {
			subtree = new SedTree<E>(this);
			subtree.insert(new ArrayList<E>(elements));
		}
		return subtree;
	}

	private E selectRoot(List<E> elements) {
		if (elements.size() < 3) return elements.get(0);
		double minDistance = Double.MAX_VALUE;
		E minRoot = null;
		for (E e : elements) {
			List<E> sublist = new ArrayList<E>(elements);
			sublist.remove(e);
			double d = distance(sublist);
			if (d < minDistance) {
				minDistance = d;
				minRoot = e;
			}
		}
		return minRoot;
	}

	public Set<E> rangeQuery(E element, double radius) {
		// TODO Auto-generated method stub
		return null;
	}

	private String toString(StringBuilder sb, SedTree<E> node) {
		if (node == null) {
			return "null";
		}
		sb.append(node.root);
		if ((node.left != null) || (node.right != null)) {
			sb.append("(\n");
			toString(sb, node.left);
			sb.append(", ");
			toString(sb, node.right);
			sb.append("\n)");
		}
		return sb.toString();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		return this.toString(sb, this);
	}

	@Override
	public MetricIndex<E> clone() {
		return new SedTree<E>(this);
	}
}
